package main

// 32. 最长有效括号
func main() {

}

func longestValidParentheses(s string) int {
	// 使用DP数组，记录以 ) 结尾的最长长度
	maxRes := 0

	sLen := len(s)
	dp := make([]int, sLen)

	for i := 1; i < sLen; i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				if i > 2 {
					dp[i] = dp[i-2] + 2
				} else {
					dp[i] = 2
				}
			} else if i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '(' { // 说明上一个是')'
				// 就把上一个之前的加进来
				if i-dp[i-1] > 2 {
					dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
				} else {
					dp[i] = dp[i-1] + 2
				}
			}
			maxRes = max(maxRes, dp[i])
		}
	}

	return maxRes
}

/**
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0


提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
*/
